package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         111,
		Discription: "二叉树的最小深度",
		Level:       1,
		Labels: map[string]int{
			"回溯":  1,
			"二叉树": 1,
		},
	})
}

func MinDepth(root *ds.TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := MinDepth(root.Left)
	rightDepth := MinDepth(root.Right)
    //注意有可能一边的子节点为空,这个时候说明不是叶子节点，得取另外一边的深度
	if leftDepth == 0 {
		return rightDepth + 1
	}
	if rightDepth == 0 {
		return leftDepth + 1
	}

	return min(leftDepth, rightDepth) + 1
}
